package _220320;


import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

// 1:无需package
// 2: 类名必须Main, 不可修改



public class Main {
    /**
     *  1.5s：超时
     */
    static long ans=0;
    static long[][] dp=new long[1<<22][22];
    static boolean[][] matrix=new boolean[22][22];
    public static void main(String[] args) {
        for(int i=1;i<22;i++)
            for(int j=i+1;j<22;j++)
                if(gcd(i,j)==1)
                    matrix[i][j]=matrix[j][i]=true;
        for(int i=0;i<1<<22;i++)
            Arrays.fill(dp[i], -1);
        dfs(1<<20,20);   //第二个参数是20代表着，我们这个状态的上一次操作是21-20=1。
        //为什么要这样设置呢，因为dfs里面用起来就方便了。有点绕，理解就好。
        System.out.println(ans);
    }

    static void dfs(int state,int pre)
    {
        if(state==(1<<21)-1)   //如果所有的点都遍历，那么ans++。
        //不用判断最后一个教学楼是否能到1号教学楼，因为1号教学楼其实和所有的教学楼都是通的。
        {
            ans++;
            return;
        }
        Queue<Integer> Q =new LinkedList<Integer>();
        for(int i=19;i>=0;i--)
        {
            if((state>>i&1)==1||!matrix[21-pre][21-i])
                continue;
            Q.add(i);
        }
        if(Q.size()==0) return;
        long t;
        while(Q.size()!=0)
        {
            if(dp[state][Q.peek()]!=-1)
            {
                ans+=dp[state][Q.peek()];
                Q.poll();
                continue;
            }
            t=ans;
            dfs(state+(1<<Q.peek()), Q.peek());
            dp[state][Q.poll()]=ans-t;   //通过上面的dfs，差值就是这个状态对应的值
        }
    }

    static int gcd(int a,int b)
    {
        if(a%b==0)
            return b;
        return gcd(b, a%b);
    }
}
